﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace storageManagement
{
    public partial class Form1 : Form
    {   
        int[] instructions = new int[320];//保存指令序列
        double[] fifo = new double[29];//保存fifo算法下4-32主存页面数的命中率
        double[] lru = new double[29];//保存lru算法下4-32主存页面数的命中率
        double[] opt = new double[29];//保存fifo算法下4-32主存页面数的命中率
        double[] lfu = new double[29];//保存lru算法下4-32主存页面数的命中率

        int k = 4;//设置主存页面数初值

        public Form1()
        {
            InitializeComponent();
        }

        private void init()          //生成随机数指令序列
        {
            richTextBox1.Clear();    //清空富文本框
            int[] a = new int[320];
            int m = 160;
            int j = 0;
            for (int i = 0; i < 80; i++)
            {
                Random random = new Random();
                int rdnum = new Random(Guid.NewGuid().GetHashCode()).Next(1, 100);//生成随机数范围1-100
                j = i * 4;
                a[j] = m;
                a[j + 1] = m + 1;
                a[j + 2] = a[j] * rdnum / 100;   //a[j+2]<=a[j]
                a[j + 3] = a[j + 2] + 1;
                m = a[j + 3] + (319 - a[j + 3]) * rdnum / 100;
            }
            richTextBox1.AppendText("页地址流如下:"+ System.Environment.NewLine);
            for (int i = 0; i < 320; i++)                               //将指令序列变换成为页地址流
            {
                instructions[i] = a[i] / 10 + 1;                        
                richTextBox1.AppendText(instructions[i] + ",");
                if (i == 319)
                    richTextBox1.AppendText(instructions[i].ToString());
            }

        }

        private void drawTable()
        {

            int h = DgvPcb.Size.Height / (29 + 2) - 1;

            DataTable dt = new DataTable();
            dt.Columns.Add(new DataColumn("主页数K", typeof(string)));  //主页数4-32
            dt.Columns.Add(new DataColumn("FIFO", typeof(string)));     //fifo算法
            dt.Columns.Add(new DataColumn("LRU", typeof(string)));      //LRU算法
            dt.Columns.Add(new DataColumn("OPT", typeof(string)));      //OPT算法
            dt.Columns.Add(new DataColumn("LFU", typeof(string)));      //LFU算法

            for (int q = 0; q < 29; q++)      //计算4-32的命中率
            {

                int mm = q + 1;

                DataRow dr;
                dr = dt.NewRow();
                dr["主页数K"] = q+4;
                string s1 = "";     //FIFO算法
                string s2 = "";     //LRU算法
                string s3 = "";     //OPT算法
                string s4 = "";     //LFU算法

                s1 = Convert.ToString(fifo[q]);
                s2 = Convert.ToString(lru[q]);
                s3 = Convert.ToString(opt[q]);
                s4 = Convert.ToString(lfu[q]);
            
                dr["FIFO"] = s1;
                dr["LRU"] = s2;
                dr["OPT"] = s3;
                dr["LFU"] = s4;

                dt.Rows.Add(dr);
                
            }
            
            DgvPcb.DataSource = dt;
            DgvPcb.RowsDefaultCellStyle.Alignment = DataGridViewContentAlignment.MiddleCenter;
            DgvPcb.ColumnHeadersDefaultCellStyle.Alignment = DataGridViewContentAlignment.MiddleCenter;
            DgvPcb.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.Fill;
            DgvPcb.RowHeadersVisible = false;
        }
        private void fifoStart()   //设置FIFO算法
        {
            
            for (k = 4; k <= 32; k++)
            {
                int[] m = new int[k];//记录当前值
                int erro = 0;//记录缺页次数
                int i = 0;

                for (int j = 0; j < instructions.Length; j++)
                {
                    if (m[0] == 0)//m为空，第一次载入
                    {
                        try
                        {
                            m[j] = instructions[j];
                            erro++;
                            i++;
                        }catch(Exception ex)
                        {
                            Application.Exit();
                            Console.WriteLine(ex.Message);
                        }
                    }
                    else
                    {
                        if (isIn(m, instructions[j]) == false)//指令不在m中
                        {
                            if (i < k)//主存未满且指令不在其中，得到返回值是未满的第一个区域
                            {
                                m[i] = instructions[j];
                                erro++;
                                i++;
                            }
                            else //主存已满则覆盖n位置
                            {
                                for (int p = 0; p < m.Length - 1; p++)
                                {
                                    m[p] = m[p + 1];        //向后移动
                                }
                                m[m.Length - 1] = instructions[j];
                                erro++;
                            }

                        }
                        else
                        {
                            if (i < k) //主存未满，且指令仍在其中
                            {
                                for (int p = 0; p < k;p++)//覆盖指令
                                {
                                    if (m[p] == instructions[j])
                                    {
                                        for (int q = p; q < k - 1; q++)
                                        {
                                            m[q] = m[q + 1];
                                        }
                                        for (int q = 0; q < k; q++)
                                        {
                                            if (m[q] == 0)
                                            {
                                                m[q] = instructions[j];   //添加指令，指令数量i不变
                                                break;
                                            }
                                        }
                                        break;
                                    }
                                   
                                }
                                  
                            }
                            else     //主存已满且，指令在其中
                            {
                                for (int p = 0; p < k; p++)//覆盖指令
                                {
                                    if (m[p] == instructions[j])//找到该指令位置为P
                                    {
                                        for (int mm = p; mm < k - 1; mm++)//覆盖指令
                                        {
                                            m[mm] = m[mm + 1];
                                        }
                                        m[k-1] = instructions[j];//主存已满则在最末尾添加数据

                                    }

                                }
                            }

                        }
                    }    

                    fifo[k - 4] = 1-Convert.ToDouble(erro)/ Convert.ToDouble(320);

                }
                
            }
           
         
        }

        private void lruStart()    //设置LRU算法
        {
            for (k = 4; k <= 32; k++)
            {
                int[] m = new int[k];//记录当前值
                int erro = 0;//记录缺页次数
                int i = 0;

                for (int j = 0; j < instructions.Length; j++)
                {
                    if (m[0] == 0)//m为空，第一次载入
                    {
                        m[j] = instructions[j];
                        erro++;
                        j++;
                    }

                    else
                    {
                        if (isIn(m, instructions[j]) == false)//指令不在m中
                        {
                            if (i < k)//主存未满且指令不在其中
                            {
                                m[i] = instructions[j];
                                erro++;
                                i++;
                            }
                            else //主存已满则覆盖n位置
                            {
                                for (int p = 0; p < m.Length - 1; p++)
                                {
                                    m[p] = m[p + 1];
                                }
                                m[m.Length - 1] = instructions[j];

                                erro++;
                            }
                        }
                        else
                        {
                            if (i < k) //主存未满，且指令仍在其中
                            {
                                for (int p = 0; p < k; p++)//覆盖指令
                                {
                                    if (m[p] == instructions[j])
                                    {
                                        for (int q = p; q < k - 1; q++)
                                        {
                                            m[q] = m[q + 1];
                                        }
                                        for (int q = 0; q < k; q++)
                                        {
                                            if (m[q] == 0)
                                            {
                                                m[q] = instructions[j];   //添加指令，指令数量i不变
                                                break;
                                            }
                                        }
                                        break;
                                    }

                                }

                            }
                            else     //主存已满且，指令在其中
                            {
                                for (int p = 0; p < k; p++)//覆盖指令
                                {
                                    if (m[p] == instructions[j])//找到该指令位置为P
                                    {
                                        for (int mm = p; mm < k - 1; mm++)//覆盖指令
                                        {
                                            m[mm] = m[mm + 1];
                                        }
                                        m[k - 1] = instructions[j];//主存已满则在最末尾添加数据

                                    }

                                }
                            }

                        }
                        lru[k - 4] = 1 - Convert.ToDouble(erro) / Convert.ToDouble(320);   //计算命中率
                    }

                }

            }
        }

        private void lfuStart() //设置LFU算法
        {
            for (k = 4; k <= 32; k++)
            {
                int min = 0;        
                int index=0;
                int[] m = new int[k];//记录当前值
                int erro = 0;//记录缺页次数
                int i = 0;
                int[] mCount = new int[k];
                int[] mFlag = new int[k];
                for(int x = 0; x < mCount.Length; x++)
                {
                    m[x] = 0;
                    
                }
                for (int j = 0; j < instructions.Length; j++)
                {
                    if(m[0] == 0)    //m为空，第一次载入
                    {
                        m[j] = instructions[j];
                        erro++;
                        j++;
                    }
                    else
                    {
                        if (isIn(m, instructions[j]) == false)//指令不在m中
                        {
                            if (i < k)//主存未满且指令不在其中
                            {
                                m[i] = instructions[j];
                                erro++;
                                i++;
                            }
                            else //主存已满则寻找则寻找最远将来才会被换出的替换
                            {
                                for (int count=0;count<j;count++)
                                {
                                    if (isIn(m, instructions[count])) //如果后续出现的数在记录的数组中，记录出现次数的数组中对应该页面数的数则+1
                                    {
                                        mCount[find(m, instructions[count])]++;
                                    }
                                }
                                min = mCount[0];
                                for(int y = 0; y < mCount.Length; y++)
                                {
                                    if (min > mCount[y])    //找出最小值
                                        min = mCount[y];
                                    index = y;              //找出最小值的下标
                                }
                                m[index] = instructions[j];
                                erro++;
                            }
                        }
                        else
                        {
                            if (i < k) //主存未满，且指令仍在其中
                            {
                                for (int p = 0; p < k; p++)//覆盖指令
                                {
                                    if (m[p] == instructions[j])
                                    {
                                        for (int q = p; q < k - 1; q++)
                                        {
                                            m[q] = m[q + 1];
                                        }
                                        for (int q = 0; q < k; q++)
                                        {
                                            if (m[q] == 0)
                                            {
                                                m[q] = instructions[j];   //添加指令，指令数量i不变
                                                break;
                                            }
                                        }
                                        break;
                                    }

                                }

                            }
                            else     //主存已满且，指令在其中
                            {
                                for (int p = 0; p < k; p++)//覆盖指令
                                {
                                    if (m[p] == instructions[j])//找到该指令位置为P
                                    {
                                        for (int mm = p; mm < k - 1; mm++)//覆盖指令
                                        {
                                            m[mm] = m[mm + 1];
                                        }
                                        m[k - 1] = instructions[j];//主存已满则在最末尾添加数据

                                    }

                                }
                            }

                        }
                        lfu[k - 4] = 1 - Convert.ToDouble(erro) / Convert.ToDouble(320);
                    }

                }
            }
        }

        private void optStart() //设置OPT算法
        {
            for (k = 4; k <= 32; k++)
            {
                int numCount = 1; ;
                int max = 0;
                int index = 0;
                int[] m = new int[k];//记录当前值
                int erro = 0;//记录缺页次数
                int i = 0;
                int[] mCount = new int[k]; //记录距离
                int[] mFlag = new int[k]; //记录最远距离对应的是哪个值
                for (int x = 0; x < mCount.Length; x++)
                {
                    m[x] = 0;
                }
                for (int j = 0; j < instructions.Length; j++)
                {

                    if (m[0] == 0)    //m为空，第一次载入
                    {
                        m[j] = instructions[j];
                        erro++;
                        j++;
                    }
                    else
                    {
                        if (isIn(m, instructions[j]) == false)//指令不在m中
                        {
                            if (i < k)//主存未满且指令不在其中
                            {
                                m[i] = instructions[j];
                                erro++;
                                i++;
                            }
                            else //主存已满则寻找则寻找最远将来才会被换出的替换
                            {
                                for (int count = j + 1; count < instructions.Length; count++)
                                {
                                    if (isIn(m, instructions[count])&& mFlag[find(m, instructions[count])]!=0) //如果后续出现的数在记录的数组中，记录出现次数的数组中对应该页面数的数则+1
                                    {
                                        mCount[find(m, instructions[count])] = count - j ;
                                        mFlag[find(m, instructions[count])] = 1;
                                        numCount++;
                                    }
                                    else if(!isIn(m, instructions[count]))
                                    {
                                        for(int x = 0; i < k; x++) //未找到，则之前的距离加1
                                        {
                                            if(mFlag[x]==0)
                                                 mCount[x]++;
                                        }
                                    }
                                }
                                max = mCount[0];
                                for (int y = 0; y < mCount.Length; y++)
                                {
                                    if (max < mCount[y])    //找出距离最大值
                                        max = mCount[y];
                                    index = y;              //找出最小值的下标
                                }
                                m[index] = instructions[j];
                                erro++;
                            }
                        }
                        else
                        {
                            if (i < k) //主存未满，且指令仍在其中
                            {
                                for (int p = 0; p < k; p++)//覆盖指令
                                {
                                    if (m[p] == instructions[j])
                                    {
                                        for (int q = p; q < k - 1; q++)
                                        {
                                            m[q] = m[q + 1];
                                        }
                                        for (int q = 0; q < k; q++)
                                        {
                                            if (m[q] == 0)
                                            {
                                                m[q] = instructions[j];   //添加指令，指令数量i不变
                                                break;
                                            }
                                        }
                                        break;
                                    }

                                }

                            }
                            else     //主存已满且，指令在其中
                            {
                                for (int p = 0; p < k; p++)//覆盖指令
                                {
                                    if (m[p] == instructions[j])//找到该指令位置为P
                                    {
                                        for (int mm = p; mm < k - 1; mm++)//覆盖指令
                                        {
                                            m[mm] = m[mm + 1];
                                        }
                                        m[k - 1] = instructions[j];//主存已满则在最末尾添加数据

                                    }

                                }
                            }

                        }
                        opt[k - 4] = 1 - Convert.ToDouble(erro) / Convert.ToDouble(320);
                    }

                }
            }
        }



        private int isFull(int[] m)//判断数组是否已满，否则返回未满的第一个位置
        {
            for (int q = 0; q < m.Length; q++)
            {
                if (m[q] == 0)
                    return q;
            }
            return -1;
        }
        private bool isIn(int[] m, int s)//判断m数组中是否有s指令
        {
            for (int q = 0; q < m.Length; q++)
            {
                if (m[q] == s)
                    return true;
            }
            return false;
        }
        private int find(int[] m,int s)//找到s指令在m数组中的下标
        {
            for(int q = 0; q < m.Length; q++)
            {
                if (m[q] == s)
                    return q;   //找到则返回下标
            }
            return -1;
        }

        private void btuStart_Click(object sender, EventArgs e)
        {
            init();                 //生成页地址流
            
        }

        private void button1_Click(object sender, EventArgs e)
        {
            if (richTextBox1.Text.Equals(""))
            {
                try
                {
                    MessageBox.Show("尚未生成页地址流！");
                }catch(Exception ex)
                {
                    Application.Exit();
                    Console.WriteLine(ex.Message);
                }

            }
            else
            {
                drawTable();
                fifoStart();
                lruStart();
                lfuStart();
                optStart();
                drawTable();
            }
        }

        private void Form1_Load(object sender, EventArgs e)
        {

        }
    }
}
